package org.lql.algo.codecrush.hot100.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 09:15
 * @description: 763. 划分字母区间 <a href="https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class PartitionLabels {

	public List<Integer> partitionLabels(String s) {
		// last数组用于记录每个字符最后一次出现的索引位置
		int[] last = new int[26];
		for (int i = 0; i < s.length(); i++) {
			// 更新字符最后一次出现的位置：a:0, b:1, c:2, ..., z:25
			last[s.charAt(i) - 'a'] = i;
		}
		// 当前片段的起始位置, 当前片段的结束位置
		int start = 0;
		int end = 0;
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			// 更新当前片段的结束位置
			end = Math.max(end, last[s.charAt(i) - 'a']);
			// 如果当前索引等于当前片段的结束位置，则划分片段并更新起始位置
			if (i == end) {
				res.add(end - start + 1);
				start = end + 1;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		PartitionLabels partitionLabels = new PartitionLabels();
		System.out.println(partitionLabels.partitionLabels("ababcbacadefegdehijhklij"));
		System.out.println(partitionLabels.partitionLabels("eccbbbbdec"));
	}
}
